#include<iostream>
using namespace std;
int main(){
	int n,V;
	cin>>V>>n;
	int v[n+1],p[n+1],dp[V+1]={0};
	for(int i=1;i<=n;++i)
		cin>>v[i]>>p[i];
	for(int i=1;i<=n;++i)
		for(int j=V;j>=v[i];--j)
			dp[j]=max(dp[j-v[i]]+p[i],dp[j]);
	cout<<dp[V];
	return 0;
}